#include "dp.h"
#include "stdio.h"
#include <string.h>
#include <stdlib.h>
#include "array_utils.h"
#include "math.h"
int longest_common_substring(char *a, char *b)
{
    int n = (int)strlen(a);
    int m = (int)strlen(b);
    int *dp = malloc((n + 1)* (m + 1) * sizeof(int));
    for(int i=0;i<(n+1)*(m+1);i++){
        dp[i]=0;
    }
    for(int i=1;i<n+1;i++){
        for(int j=1;j<m+1;j++){
            int index=i*(m+1)+j;
        int prev_index=(i-1)*(m+1)+j-1;
            if(a[i-1]==b[j-1]){
               dp[index]=dp[prev_index]+1;
            }else{
                dp[index]=0; 
            }
        }
    }
    int max=0;
    for(int i=0;i<(n+1)*(m+1);i++){
        if(dp[i]>max){
            max=dp[i];
        } 
    }
    free(dp);
    return max;
};

int knapstack01(int weights[], int values[], int w, int len) {
    int **dp;
    ALLOCATE_2D_ARRAY(&dp, int, len + 1, w + 1, return -1);


    // 初始化dp表
    for (int i = 0; i <= len; i++) {
        for (int j = 0; j <= w; j++) {
            dp[i][j] = 0;
        }
    }

    // 0-1 背包问题核心逻辑
    // i 代表物品索引 (从1到len)，j 代表当前背包容量 (从1到w)
    // weights 和 values 数组是0索引的，所以第i个物品对应 weights[i-1] 和 values[i-1]
    for (int i = 1; i <= len; i++) {
        for (int j = 1; j <= w; j++) {
            if (weights[i - 1] <= j) { // 如果第i个物品的重量小于等于当前容量
                // 选择不放入第i个物品: dp[i-1][j]
                // 选择放入第i个物品: values[i-1] + dp[i-1][j - weights[i-1]]
                int value_if_not_taken = dp[i - 1][j];
                int value_if_taken = values[i - 1] + dp[i - 1][j - weights[i - 1]];
                dp[i][j] = (value_if_taken > value_if_not_taken) ? value_if_taken : value_if_not_taken;
            } else { // 如果第i个物品的重量大于当前容量，则不能放入
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    int result = dp[len][w];

    // 释放内存
    FREE_2D_ARRAY(dp, len + 1);

    return result;
}